The present invention relates to decoding of codewords and, more particularly, to a LDPC decoding method that uses serial updating of the messages of only selected is nodes in each iteration.
Low-density parity check (LDPC) codes are a class of linear block codes. The name “LDPC” comes from the fact that the parity-check matrices of these codes have many more zeros than ones. The main advantages of LDPC codes are that they provide a performance that is very close to capacity for many different channels, that their decoding algorithms have linear complexity in time, and that they are suited for implementations that make heavy use of parallelism.
LDPC codes were first introduced by R. G. Gallager in 1960 in his PhD thesis. Due to the computational effort required to implement LDPC coders and decoders, and due to the introduction of Reed-Solomon codes, LDPC codes were generally ignored until the mid-1990s.
LDPC codes may be represented either as matrices or graphically.
The following matrix is an example of a m×n parity check matrix for a (8,4) code (m=4, n=8):
  H  =      (                            0                          1                          0                          1                          1                          0                          0                          0                                      1                          1                          1                          0                          0                          1                          0                          0                                      0                          0                          1                          0                          0                          1                          1                          1                                      1                          0                          0                          1                          1                          0                          1                          0                      )  
Two numbers describe such matrices: wr, the number of ones in a row, and wc, the number of ones in a column. For such a matrix to be “low density”, wr must be much less than m and wc must be much less than n. This is not the case in the above example but it is the case in the much larger parity check matrices that are used in practice.
In 1981, Tanner introduced an effective graphical representation of LDPC codes. These graphs both provide a complete representation of such codes and also help to describe decoding algorithms.
A Tanner graph is a “bipartite” graph. This means that the nodes of the graph are separated into two distinct sets and that the edges of the graph connect nodes of different types. The two types of nodes in a Tanner graph are the variable nodes (or v-nodes) and the check nodes (or c-nodes).
FIG. 1 shows a Tanner graph that represents the same code as the above matrix. The graph has m check nodes (m is the number of parity bits) and n variable nodes (n is the number of bits in a codeword). Check node f is connected to variable node c1 if the element hij of H is a one.
A LDPC code is called “regular” if every column has the same number of ones (wc constant) and every row has the same number of ones (wr constant). The matrix above is regular with wc=2 and wr=4. The regularity of this code also is evident in FIG. 1: every v-node has the same number of incoming edges and every c-node has the same number of incoming edges. If a parity check matrix is low density but the number of ones in each row or column is not constant the code is called an “irregular” LDPC code.
The basic algorithm used to decode LDPC codes was discovered independently several times and is called by different names. The most common names are “belief propagation algorithm”, “message passing algorithm” and “sum-product algorithm”.
The algorithm assumes that estimates of the bits of the codeword to be decoded are provided in the form of log-likelihood-ratios (LLRs)
      P    i    =            log      ⁡              (                              Pr            ⁡                          (                                                bit                  ⁢                                                                          ⁢                  i                                =                0                            )                                            Pr            ⁡                          (                                                bit                  ⁢                                                                          ⁢                  i                                =                1                            )                                      )              .  These LLR estimates can be computed e.g. based on symbols received from a noisy channel. At the end of every iteration, the current estimate of the LLR of the i-th bit is denoted Qi. The message sent by variable node ci to check node fj is denoted Qij. The message sent by check node fj to variable node ci is denoted Rji. Initially, for all i and j, Qij=Pi and Rji=0. In each iteration the messages are computed according to the following updating rules:
            Q      ij        ←                  P        i            +                        ∑                                    j              ′                        ∈                                          N                ⁡                                  (                  i                  )                                            ⁢              \              ⁢              j                                      ⁢                  R                                    j              ′                        ⁢            i                                          R      ji        ←                  φ                  -          1                    (                        ∑                                    i              ′                        ∈                                          N                ⁡                                  (                  j                  )                                            ⁢              \              ⁢              i                                      ⁢                  φ          ⁡                      (                          Q                                                i                  ′                                ⁢                j                                      )                              )                  Q      i        ←                  P        i            +                        ∑                      j            ∈                          N              ⁡                              (                j                )                                                    ⁢                  R          ji                    where N(k) denotes the set of neighbors of a node k, i.e., in the case of k=i, all the check nodes fj that send messages to a given variable node ci, and in the case of k=j, all the variable nodes ci that send messages to a given check node fj; and
            φ      ⁡              (        x        )              =          (                        sign          ⁢                                          ⁢                      (            x            )                          ,                              -            log                    ⁢                                          ⁢                      tanh            (                                                          x                                            2                        )                              )                          φ                  -          1                    ⁡              (        x        )              =                            (                      -            1                    )                sign            ⁢              (                              -            log                    ⁢                                          ⁢                      tanh            ⁡                          (                              x                2                            )                                      )            Note that φ(x) and its computations are defined over a group F2×[0,∞]. If the message sent by variable node ci to check node fj is re-defined as Tij=φ(Qij), symmetric updating rules can be expressed as follows.
            T      ji        ←          φ      (                        P          i                +                              ∑                                          j                ′                            ∈                                                N                  ⁡                                      (                    i                    )                                                  ⁢                \                ⁢                j                                              ⁢                      R                                          j                ′                            ⁢              i                                          )                  R      ji        ←                  φ                  -          1                    (                        ∑                                    i              ′                        ∈                                          N                ⁡                                  (                  j                  )                                            ⁢              \              ⁢              i                                      ⁢                  T                                    i              ′                        ⁢            j                              )      
The order of passing messages among the nodes is referred to as a message passing decoding schedule. The conventional message-passing schedule is the “flooding” schedule (R. C. Gallager, Low-Density Parity-Check Codes, MIT Press, 1963), in which, in each iteration, first all the variable nodes pass new messages to their neighbors, and then all the check nodes pass new messages to their neighbors. A serial schedule in which an iteration is performed by serially traversing the variable nodes and for each one updating its incoming and outgoing messages was shown in E. Sharon, S. Litsyn and J. Goldberger, “Efficient serial message-passing schedules for LDPC decoding”, Proc. Turbo-Coding-2006 Conference, Munich, April 2006, to converge approximately twice as fast as the flooding schedule.
The following U.S. patents are representative of the state of the art in LDPC encoding and decoding:
U.S. Pat. No. 7,089,479 to Matsumoto
U.S. Pat. No. 7,107,511 to Shen et al.
U.S. Pat. No. 7,120,857 to Kim et al.
U.S. Pat. No. 7,127,659 to Richardson et al.
U.S. Pat. No. 7,133,853 to Richardson et al.
U.S. Pat. No. 7,149,953 to Cameron et al.
U.S. Pat. No. 7,174,495 to Boutillon et al.
U.S. Pat. No. 7,181,676 to Hocevar
All of these patents are incorporated by reference for all purposes as if fully set forth herein.